package com.njupt.StackAndQueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/24 14:53
 * @Description: 单调递增队列
 * @Version: 1.0
 */


//构建单调递增队列
public class MonotonicIncQueue {

    private Deque<Integer> monotonicIncQueue = new LinkedList<>();


    //往队列中添加元素时，要保证添加的元素满足队列中的单调性
    public void push(int val){
        while(!monotonicIncQueue.isEmpty() && val<monotonicIncQueue.getLast()){
            monotonicIncQueue.removeLast();
        }
        monotonicIncQueue.addLast(val);

    }

    //取队头元素
    public void poll(int val){
        if(!monotonicIncQueue.isEmpty() && val == monotonicIncQueue.peekFirst()){
            monotonicIncQueue.removeFirst();
        }
    }

    public int peek(){
        return monotonicIncQueue.peekFirst();
    }

    public static void main(String[] args) {
        MonotonicIncQueue incQueue = new MonotonicIncQueue();
        incQueue.push(5);
        incQueue.push(8);
        incQueue.push(2);
        incQueue.push(4);
        incQueue.push(1);
        System.out.println(incQueue.monotonicIncQueue.toString());

    }
}
